package lcr;

import java.util.ArrayList;
import java.util.List;

public class Test0100 {

    public static void main(String[] args) {
        Solution0100_1 solution = new Solution0100_1();
        ArrayList<List<Integer>> list = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(2);
        ArrayList<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);

        ArrayList<Integer> list3 = new ArrayList<>();
        list3.add(5);
        list3.add(6);
        list3.add(7);
        ArrayList<Integer> list4 = new ArrayList<>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);

        list.add(list1);
        list.add(list2);
        list.add(list3);
        list.add(list4);
        System.out.println(solution.minimumTotal(list));
    }
}

class Solution0100_1 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        if (size<=1) return triangle.get(0).get(0);
        int ans=Integer.MAX_VALUE;

        for (int i = 1; i < size; i++) {
            List<Integer> list = triangle.get(i);
            List<Integer> pre = triangle.get(i-1);
            int size1 = list.size();
            int size2 = pre.size();
            for (int j = 0; j < size1; j++) {
                Integer now = list.get(j);
                if (j-1>=0&&j<size2) now += Math.min(pre.get(j - 1), pre.get(j));
                else if (j-1>=0||j<size2) now += j - 1 >= 0 ? pre.get(j - 1) : pre.get(j);
                list.set(j, now);

                if (i==size-1) ans=Math.min(ans,now);
            }
        }

        return ans;
    }
}

